package jianzhiOffer;
//剑指 Offer 33. 二叉搜索树的后序遍历序列
public class Num33_verifyPostorder {
    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorderHelper(postorder,0,postorder.length-1);
    }
    private boolean verifyPostorderHelper(int[] postorder, int start, int end) {
        if (start>=end){
            return true;
        }
        int root = postorder[end];
        int i = start;
        while (i<end && postorder[i]<root){
            i++;
        }
        for (int j = i; j < end; j++) {
            if (postorder[j] < root){
                return false;
            }
        }
        return verifyPostorderHelper(postorder,start,i-1)&&verifyPostorderHelper(postorder,i,end-1);
    }

}
